// 基本思想：前i-1个元素为已排序部分，后n-i+1为未排序部分，第i趟排序从未排序部分选择最小的值并与未排序部分的首位交换位置
// 简单来说,选择排序在每趟排序中,从未排序部分中选出一个值最小的元素与未排序部分的第一个元素交换位置,从而将该元素划分到已排序部分

// 时间复杂度：从是O(n^2)
// 排序稳定性：不稳定

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }            
        }  
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }      
    }
    return arr
}

let arr = [6, 2, 4, 3, 3, 5, 1, 4]

console.log(selectionSort(arr))